

//
//  LinkedList_search.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/9.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 有序列表查找
extension LinkedList where Element: Comparable {
    
    /// 在节点p的n个真后继(不包括p)中查找不小于element的第一个元素
    public func search(_ element: Element, _ p: LinkedListNode<Element>, _ n: Int) -> LinkedListNode<Element>? {
        precondition(n >= 0, "\(n)不能小于0")
        var index = 1
        var nd = p.successor
        while let node = nd, node !== _trailer {
            if index > n { return nil }
            if node.value! >= element {
                return node
            }
            index += 1
            nd = node.successor
        }
        
        return nil
    }
    
    /// 在节点p的n个真前驱(不包括p)中查找不大于element的最后一个元素
    public func search(_ element: Element, _ n: Int, _ p: LinkedListNode<Element>) -> LinkedListNode<Element>? {
        precondition(n >= 0, "\(n)不能小于0")
        var index = 1
        var nd = p.predecessor
        while let node = nd, node !== _header {
            if index > n { break }
            if node.value! <= element {
                return node
            }
            index += 1
            nd = node.predecessor
        }
        
        return nil
    }
    
}
